KURZUS: Alkalmazott operációkutatás

MODUL: II. modul: Egészértékű programozási feladat fogalma és grafikus megoldása. Néhány nevezetes egészértékű modell

9. lecke: Nemlineáris programozás

|  | Tanulási útmutató
| A nemlineáris programozás fogalma, grafikus szemléltetése és gyakorlati példák a tankönyv 7. fejezetében találhatók.
| A közgazdaságban kitüntetett szerepe van a tört- vagy hiperbolikus programozásnak, ezért a tankönyv kiemelten csak ennek a feladattípusnak az algebrai megoldását tárgyalja. Ez található meg a tankönyv 7.3. alfejezetében. Figyelmesen tanulmányozza át a tankönyvben található módszert, mert ez azt mutatja be, hogy hogyan lehet lineáris programozási feladatra visszavezetni és szimplex módszerrel megoldani.
| Tevékenységek
| Figyelmesen olvassa el a tankönyvben található hiperbolikus programozás definícióját és jól jegyezze meg a mátrixvektor szimbólumokkal adott modelljét
| A tankönyvben látható gyakorlati példára alkalmazza a "transzformációt". Vezesse be az y j és a t új változókat. Vegyen elő egy lapot és írja fel a feladat lineáris programozási modelljét.
| A nemlineáris programozási feladatok megoldása Solver programmal.
| A Solver program lehetővé teszi a nemlineáris célfüggvényű programozási feladatok megoldását is. A már korábban bemutatott Beállítások lenyíló menüben nem kell bejelölni a Lineáris modellt feltételez előtt álló jelölőnégyzetet!
| Követelmények
| Kulcsszavak alapján ki tudja egészíteni a nemlineáris programozásra, a kvadratikus, illetve hiperbolikus programozásra vonatkozó mondatot. Az egyes programozási modellekre vonatkozó állításokról el tudja dönteni, hogy igazak vagy hamisak. Egy adott hiperbolikus programozási feladat modelljét át tudja transzformálni lineáris programozási feladattá! Solver segítségével meg tud oldani nemlineáris programozási feladatokat!

|  | Bemutató feladat
| 1. Oldjuk meg Simplex módszer segítségével az alábbi feladatot!
| x 1 ; x 2 ; x 3 ≥0 2 x 1 +2 x 2 ≤6 x 1 + x 2 + x 3 ≤4 2 x 1 + x 2 + x 3 −1 x 1 + x 2 + x 3 +1 →max
| Vezessünk be új ismereteket!
| 2 y 1 +2 y 2 −6 t≤0 y 1 + y 2 + y 3 −4 t≤0 y 1 + y 2 + y 3 +t=1 2 y 1 + y 2 + y 3 −t→max
B0 | y1 | y2 | y3 | t |
w1 | 2 | 2 | 0 | -6 | 0
w2 | 1 | 1 | 1 | -4 | 0
u3 | 1 | 1 | 1 | 1 | 1
-z | 2 | 1 | 1 | -1 | 0
B1 | y1 | y2 | y3 | u3 |
w1 | 8 | 8 | 6 | 6 | 6
w2 | 5 | 5 | 5 | 4 | 4
t | 1 | 1 | 1 | 1 | 1
-z | 3 | 2 | 2 | 1 | 1
B2 | w1 | y2 | y3 | u3 |
y1 | 1/8 | 1 | 3/4 | 3/4 | 3/4
w2 | -5/8 | 0 | 1 1/4 | 1/4 | 1/4
t | -1/8 | 0 | 1/4 | 1/4 | 1/4
-z | -3/8 | -1 | -1/4 | -1 1/4 | -1 1/4
y1=3/4 | y2=0 | y3=0 | t=1/4
x1=y1/t=3 | x2=y2/t=0 | x3=y3/t=0 |
| 2. Példaként nézzük a tankönyvben látható kvadratikus programozási feladat Solverrel történő megoldását. Helyezze el a modell paramétereit az Excel-táblán az alábbiak szerint:
| Korlátozó feltételek (egyenként kell felvenni őket):
| $D$3<=$F$3 $D$4<=$F$4
| Hívja meg a Solver programot és jelölje be a kért adatokat. A Beállítás menüben ne feledje el bejelölni, hogy ez nem lineáris modell (azaz ne tegyen jelet a Lineáris modellt feltételez négyzetbe)! Oldja meg a feladatot! A grafikus megoldáson látható értékeket kapja megoldásként.
| Hasonlóan oldja meg a tankönyvben látható 7.1.2. példát. Javaslat az Excel-táblázaton való elhelyezésre: Vigye be az adatokat! A B7 cellába írja be a számláló képletét, a B8 cellába a nevező képletét.
| A célfüggvény képletét az E9 cellába írjuk be.
| Hívjuk be a Solvert, és adjuk meg a feltételeket. A beállítás menüben csak a nem negatív feltételezést jelöljük be!
| Korlátozó feltételek (egyenként kell felvenni őket):
| $E$3<=$G$3 $E$4=$G$4 $E$5<=$G$5
| A megoldás gombra kattintva láthatjuk az eredményt

|  | Önellenőrző feladat
| 1. Fogalmazza meg az alábbi kulcsszavak felhasználásával a nemlineáris és a hiperbolikus programozás fogalmát, valamint a gazdasági jelentőségét.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
költség | elsőfokú | nemlineáris | másodfokú | tört | nemnegatív | árbevétel | hatvány
| a) Írja be a fenti számokat a megfelelő helyre! Nemlineáris programozásról akkor beszélünk, ha a modell feltételrendszere egyenlőtlenségrendszer, célfüggvénye pedig függvény.
| b) Írja be a fenti számokat a megfelelő helyre! Kvadratikus programozásról akkor beszélünk, ha a modell feltételrendszere egyenlőtlenség rendszer, a célfüggvénye pedig függvény.
| c) Írja be a fenti számokat a megfelelő helyre! Hiperbolikus programozásról akkor beszélünk, ha a modell feltételrendszere egyenlőtlenség rendszer, a célfüggvénye pedig függvény, azaz számlálója , a nevezője függvény.
| d) Írja be a fenti számokat a megfelelő helyre! Hiperbolikus programozási modell alkalmas arra, hogy megfogalmazzuk azt a célt, hogy az 1 Ft ráfordításra jutó nyereség legyen a legnagyobb azzal, hogy a számlálóba és függvények különbségét írjuk, a nevezőbe pedig a(z) függvényt.
| 2. Döntse el, hogy az alábbi állítások igazak vagy hamisak!
Nemlineáris programozási modellben mind a feltételrendszer mind a célfüggvény nem lineáris. |
Hiperbolikus programozási modellben csak a célfüggvény hatványfüggvény, a feltételrendszer lineáris rendszer. |
Kvadratikus programozási modellben a feltételrendszer lineáris, a célfüggvény pedig másodfokú függvény. |
Hiperbolikus programozási modellben a célfüggvény elsőfokú törtfüggvény, a feltételrendszer pedig elsőfokú egyenlőtlenségekből áll. |
Hiperbolikus programozási modellel a ráfordítás hatékonyságát, mint kívánatos célt tudjuk megfogalmazni. |
| 3. Egy hiperbolikus programozási feladat matematikai modellje a következőképpen néz ki:
| x 1 x 2 x 3 ≥ 0 2 x 1 + x 2 − x 3 ≤ 10 x 2 +2 x 3 = 8 x 1 +5 x 2 ≤ 12 z= 3 x 1 +5 x 2 + x 3 −3 x 1 +2 x 2 + x 3 +1 → max⁡
| Transzformálja át új változók bevezetésével lineáris modellé. Vegyen elő egy munkalapot, írja le a lineáris modellt, majd ezután értelem szerint töltse ki az alábbi táblázatot:
| A modell változói, egyenlőtlenségei és együtthatói, reláció jelei, valamint a jobb oldal értékei:
A nagyobb egyenlő és a kisebb egyenlő relációkat így adja meg: <= és >=! | Írja ezeket a mellékelt táblázat megfelelő helyére!
Változók | y 1 | y 2 | y 3 | t | reláció | jobb oldal
Együtthatók |  |  |  |  |  |
célfüggvény |  |  |  |  |  |
| 4. Oldja meg a Solver segítségével a következő matematikai programozási feladatot!
| x 1 x 2 x 3 ≥ 0 2 x 1 + x 2 +2 x 3 ≤ 20 x 1 + x 2 ≤ 15 x 2 + x 3 ≥ 10 z= 2 x 2 +2 x 1 + x 2 + x 3 +1 → max⁡
| Váltson át az Excel táblázatkezelőre!
| A gyors megoldás érdekében javaslom a következőt: A változók helyének kijelölése után a feltételek bal oldalának képleteit írja be egy-egy cellába. Hasonlóan a célfüggvény képleteit. Ezután hívja meg a Solver programot.
Megjegyzés: az eredményeket egész számra kerekítse! | Az optimális megoldás eredményét írja ide. x 1 = x 2 = x 3 = z o p t =